package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * https://leetcode.com/problems/longest-valid-parentheses/
 *
 * @author tzp
 * @since 2020/9/24
 */
public class LC32 implements DynamicProblem {
    public int longestValidParentheses(String s) {
        if (s.length() <= 1) return 0;
        int[] dp = new int[s.length()];//f(i), 以i为结尾的最长有效括号串的长度
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i < s.length(); i++) {//(())))
            if (s.charAt(i) == '(') {
                dp[i] = 0;
            } else {
                boolean valid = false;
                int j = i - 1;
                while (j >= 0) {
                    if (dp[j] > 0) {//j处是)且有pair的
                        dp[i] += dp[j];
                        j -= dp[j];
                    } else if (s.charAt(j) == '(') {//j处是(
                        if (!valid) {
                            dp[i] += 2;
                            valid = true;
                            j--;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if (!valid) dp[i] = 0;
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new LC32().longestValidParentheses("(())))"));
        System.out.println(new LC32().longestValidParentheses(")()())"));
    }
}
